package Tree;

import java.util.TreeSet;

/**
 * 题目 ：值和下标之差都在给定的范围内
 * 题目详述 ：
 * 给你一个整数数组 nums 和两个整数k 和 t 。
 * 请你判断是否存在 两个不同下标 i 和 j，使得abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
 * 如果存在则返回 true，不存在返回 false。
 */
public class ContainsNearbyAlmostDuplicate {
    // 明明Integer类型能够取值取到 [-2的-31次方 ~ 2的31次方-1]，为什么会报错
    // 解决 ：即，在进行所遍历到元素相互之间的差值会到 2的32次方，从而超出Integer类型所能够表示的范围
    // 知识点 ：Integer类型占用4个字节；
    /**
     * 核心思想 ：
     * 方法一 ：使用TreeSet数据结构，来存储当前遍历的数组元素的前k个数组元素；
     * 原因 ：会在遍历整个整数数组中元素的过程中，与当前元素的前k个元素进行值比较；
     * 使用TreeSet来存储前k个元素，然后使用当前元素和前k个元素进行比较，
     * （1）和前k个元素中小于当前元素值的最大键进行比较，若是成立的话，即满足题目条件；
     * （2）和前k个元素中大于当前元素的最小键进行比较，若是成立的话，即满足题目条件；
     */
//    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//        TreeSet<Long> treeSet = new TreeSet<>();
//        /**
//         *  思考 ：
//         *  为何只需要去遍历当前数组元素的前k个元素？
//         *  原因 ：
//         *  （1）若是遍历当前正在遍历的数组元素的前/后k个元素的话，会出现大量的重复遍历，导致效率降低；
//         *  （2）若是仅仅去遍历当前正在遍历的数组元素的前k个元素的话，不会出现重复的遍历，因为每次都是两个之前为比较过的元素进行比较
//         */
//        for(int i = 0 ; i < nums.length ; i++){
//            // 当前元素值 和 前k个元素中小于当前元素的最大值 进行比较；
//            // 时间复杂度 ：O（log k）
//            Long floor = treeSet.floor((long)nums[i]);
//            if (floor != null && ((long)nums[i] - floor) <= t){
//                return true;
//            }
//            // 当前元素值 和 前k个元素中大于当前元素的最小值 进行比较
//            // 时间复杂度 ：O（log k）；
//            Long higher = treeSet.higher((long)nums[i]);
//            if (higher != null && (higher - (long)nums[i]) <= t){
//                return true;
//            }
//            // 向treeSet中加入当前遍历的数组元素
//            treeSet.add((long)nums[i]);
//            if (i >= k){
//                // TreeSet移除元素需要指定所要移除元素的值；
//                // 即，同时需要去移除TreeSet中的数组的首元素
//                treeSet.remove((long)nums[i - k]);
//            }
//        }
//        return false;
//    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：遍历整个数组，时间复杂度O（n）；同时，使用TreeSet去查找元素，时间复杂度为O（log k）；
     *  即，总的时间复杂度 ：O（nlog k）
     * （2）空间复杂度 ：由于使用TreeSet数据结构，来存储当前遍历的数组元素的前k个元素；
     *  即，总的空间复杂度 ：O（k）；
     */
}
